package com.demo.example.hot100;

import java.util.*;

//双指针法，先进行排序再进行双指针遍历
public class FindTheSumOfThreeNums {
    public static void main(String[] args) {
        int[] nums=new int[]{-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        List<List<Integer>> lists = threeSum(nums);
        for(int i=0;i< lists.size();i++){
            List<Integer> list=lists.get(i);
            for(int tmp:list){
                System.out.print(tmp+"  ");
            }
            System.out.println();
        }
    }
    public static List<List<Integer>> threeSum(int[] nums){
        if(nums==null){
            return null;
        }
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int tmp=nums[i];
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                int sum=tmp+nums[left]+nums[right];
                if(sum==0){
                    List<Integer> list=new ArrayList<>();
                    list.add(tmp);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    if(!isContain(res,list)){
                        res.add(list);
                    }
                    left++;
                }else if(sum<0){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return res;
    }
    public static boolean isContain(List<List<Integer>> res,List<Integer> list){
        if(res.isEmpty()){
            return false;
        }
        for(int i=0;i<res.size();i++){
            List<Integer> tmp=res.get(i);
            Queue<Integer> queue=new LinkedList<>();
            queue.add(tmp.get(0));
            queue.add(tmp.get(1));
            queue.add(tmp.get(2));
            for(int j=0;j<3;j++){
                if(queue.contains(list.get(j))){
                    queue.remove(list.get(j));
                }
            }
            if(queue.isEmpty()){
                return true;
            }
        }
        return false;
    }
}
